package com.lcm.algorithm.datatest.array;

import java.util.Arrays;

/**
 * @description: 75.一个数组只有0,1,2，进行排序
 * 输入: [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * @author: lcm
 * @create: 2020-04-02 15:02
 **/

public class SortColors {

    public static void main(String[] args){
        //int[] array=new int[]{2,0,2,1,1,0};
        int[] array=new int[]{2,0,1};
        sortColors(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 1.暴力，直接使用快排，时间复杂度O(nlgn)
     * 2.遍历两次，一次记录各个数的数量，第二次遍历全部放入
     * 3.三指针法：
     * 0的最左可交换
     * 当前指针
     * 2的最右可交换
     * 当前为0，和p0交换；当前为2，和p2交换；当前为1，下一个。
     * @param nums
     */
    public static void sortColors(int[] nums){
        int p0=0,j=0,p2=nums.length-1;
        while (j<=p2){
            if(nums[j]==1){
                j++;
            }else if(nums[j]==2){
                int temp=nums[j];
                nums[j]=nums[p2];
                nums[p2]=temp;
                p2--;
            }else{
                int temp=nums[j];
                nums[j]=nums[p0];
                nums[p0]=temp;
                p0++;
                j++;
            }
        }
    }

}
